class Solution(object):
    # 贪心策略
    def maxProfit(self, prices):
        now=prices[0]
        profit=0
        for e in prices:
            if e-now>0:
                profit+=e-now
            now=e
        return profit
    # 动态规划
    def dp(self,prices):
        buy=[0]*len(prices)
        sold=[0]*len(prices)
        buy[0]=-prices[0]
        sold[0]=0
        
        for i in range(1,len(prices)):
            # 解释一下这两句话的含义
            '''
            这里 buy表示手里有股票的最大利润
            sold表示手里没股票的最大利润
            注意审题，手里最多持有一只股票
            所以状态转移只有两种，要么手里持有股票，要么手里没有股票
            如果手里持有股票，可能为之前已经持有了股票，或者卖出了股票并买入今天的
            如果手中没有股票，可能为之前就没买股票，或者在今天卖出了股票
           
            
            '''
            buy[i]=max(buy[i-1],sold[i-1]-prices[i])
            sold[i]=max(sold[i-1],buy[i-1]+prices[i])
        return sold[-1]
            
        
x=Solution()
dock=[7,1,5,3,6,4]
print(x.maxProfit(dock))
print(x.dp(dock))